package code801_900.code50_60;

import java.util.*;

/**
 * 有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。
 * 为了方便起见，我们将编号为 x 的人简称为 "person x "。
 *
 * 给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。
 * 另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。richer 中所给出的数据 逻辑自恰
 * （也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。
 *
 * 现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，
 * person y 是最安静的人（也就是安静值 quiet[y] 最小的人）。
 *
 * 输入：richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
 * 输出：[5,5,2,5,4,5,6,7]
 * 解释：
 * answer[0] = 5，
 * person 5 比 person 3 有更多的钱，person 3 比 person 1 有更多的钱，person 1 比 person 0 有更多的钱。
 * 唯一较为安静（有较低的安静值 quiet[x]）的人是 person 7，
 * 但是目前还不清楚他是否比 person 0 更有钱。
 * answer[7] = 7，
 * 在所有拥有的钱肯定不少于 person 7 的人中（这可能包括 person 3，4，5，6 以及 7），
 * 最安静（有较低安静值 quiet[x]）的人是 person 7。
 * 其他的答案也可以用类似的推理来解释。
 *
 * 输入：richer = [], quiet = [0]
 * 输出：[0]
 */
public class _851loudAndRich {

    /**
     * 方法1，深度优先搜索，先选出所有大于当前节点的人，在遍历每个人的quiet，最终写到结果数组中。
     *
     * 此方法看起来可行,也通过了部分测试用例.但最终在大量数据面前,超出了时间限制.
     *
     * @param richer
     * @param quiet
     * @return
     */
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int[] result = new int[quiet.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = -1;
        }
        int minQuiet;
        int minIndex;
        // 遍历每个人，找出大于他的人。
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < quiet.length; i++) {
            stack.push(i);
            minQuiet = quiet[i];
            minIndex = i;
            // 不用建立单独的数组空间存储比当前更富有的人，每次记录最小值就行.
            while (!stack.isEmpty()){
                int nowPerson = stack.pop();
                for (int j = 0; j < richer.length; j++) {
                    if(richer[j][1]==nowPerson){
                        // 就算添加了终止判断条件 还是会超出时间限制
                        if(result[richer[j][0]]!=-1&&minQuiet>quiet[result[richer[j][0]]]){
                            minIndex = result[richer[j][0]];
                            minQuiet = quiet[minIndex];
                            continue;
                        }
                        if(quiet[richer[j][0]] < minQuiet){
                            minQuiet = quiet[richer[j][0]];
                            minIndex = richer[j][0];
                        }
                        stack.push(richer[j][0]);
                    }
                }
            }
            result[i] = minIndex;
        }
        return result;
    }


    /**
     * 题解中的第一种方法,同样是深度优先遍历,主要观察为什么没有超时.
     * 最安静的人要么是自己,要么是邻居中最安静的人,如果结果中有邻居的最安静值,则可以不用计算,直接获取即可.
     *
     * 执行用时：     * 6 ms     * , 在所有 Java 提交中击败了     * 89.30%     * 的用户
     * 内存消耗：     * 46.8 MB     * , 在所有 Java 提交中击败了     * 58.14%     * 的用户
     * @param richer
     * @param quiet
     * @return
     */
    public int[] loudAndRich1(int[][] richer, int[] quiet) {
        int n = quiet.length;
        // 空间换时间,使用二维链表存储比当前更富有的人的情况.
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<Integer>();
        }
        for (int[] r : richer) {
            g[r[1]].add(r[0]);
        }

        //初始化结果集
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        // 对每个结果集进行深搜.行文至此,看不到此方法对比上述方法有什么优化的地方.
        for (int i = 0; i < n; ++i) {
            dfs(i, quiet, g, ans);
        }
        return ans;
    }

    /**
     * 方法一主要在这块添加了一个-1的结束循环.减少了工作量:已经找到后,就不用再继续找了
     * @param x
     * @param quiet
     * @param g
     * @param ans
     */
    public void dfs(int x, int[] quiet, List<Integer>[] g, int[] ans) {
        if (ans[x] != -1) {
            return;
        }
        ans[x] = x;
        for (int y : g[x]) {
            dfs(y, quiet, g, ans);
            if (quiet[ans[y]] < quiet[ans[x]]) {
                ans[x] = ans[y];
            }
        }
    }

    /**
     * 官方方法二:拓扑排序
     * 可以换个思路,将richer数组的对应关系全部反向,这样可以得到一个有向无环图.
     * 我们可以从图上任意一点出发,沿着有向边所能访问到的点,拥有的钱都比x少.这意味着我们可以计算ans[x]后,用ans[x]更新x所能访问到的点的ans值
     * 要实现此方法,可以将每个ans初始化为x,然后对图进行一遍拓扑排序,并按照排序去更新ans值.通过这一方法就能将ans值传播到x能访问到的点上.
     *
     * 但好像效率没有多少提升
     * 执行用时：     * 9 ms     * , 在所有 Java 提交中击败了     * 58.14%     * 的用户
     * 内存消耗：     * 46.8 MB     * , 在所有 Java 提交中击败了     * 40.00%     * 的用户
     * @param richer
     * @param quiet
     * @return
     */
    public int[] loudAndRich2(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<Integer>[] g = new List[n];
        for (int i = 0; i < n; ++i) {
            g[i] = new ArrayList<Integer>();
        }
        int[] inDeg = new int[n];
        for (int[] r : richer) {
            g[r[0]].add(r[1]);
            ++inDeg[r[1]];
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            ans[i] = i;
        }
        Queue<Integer> q = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            if (inDeg[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int x = q.poll();
            for (int y : g[x]) {
                if (quiet[ans[x]] < quiet[ans[y]]) {
                    ans[y] = ans[x]; // 更新 x 的邻居的答案
                }
                if (--inDeg[y] == 0) {
                    q.offer(y);
                }
            }
        }
        return ans;
    }
}
